package com.heima.leetcode.datastructure.hashtable;

import java.util.HashMap;

/**
 * <h3><strong>在数组中找到满足要求的两个数索引，要求为两个数之和 = target  1</strong></h3>
 * <h3><strong>注：给定的数组中只有一对满足条件</strong></h3>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/25 23:02
 */
public class TwoSum {

    /**
     * <h3>方法一，复杂度O(N^2)</h3>
     * 原始方法，遍历到一个数，就循环遍历后面的每一个数看有没有满足要求
     * @param nums 数组
     * @param target 两数之和
     * @return 两数的索引
     */
    public static int[] twoSum1(int[] nums, int target){
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int expect = target - nums[i];
            for (int j = i + 1; j < nums.length; j++){
                if (nums[j] == expect){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return null;
    }

    /**
     * <h3>方法二，复杂度O(N)</h3>
     * 借助哈希表解决，建立哈希表，键存数组元素，值存数组索引，遍历数组，在哈希表中查找是否有匹配的键值，找到了，返回结果，没找到，则将当前元素和索引存入哈希表
     * @param nums 数组
     * @param target 两数之和
     * @return 两数的索引
     */
    public static int[] twoSum2(int[] nums, int target){
        int[] result = new int[2];
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int expect = target - nums[i];
            Integer index = hashMap.get(expect);
            if (index == null){
                hashMap.put(nums[i], i);
            }else {
                result[0] = index;
                result[1] = i;
                return result;
            }
        }
        return null;
    }
}
